#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; i++) {
            ret[i].resize(i + 1, 1);
            for (int j = 0; j < i; j++) {
                if (i >= 2 && j >= 1) {
                    ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
                }
            }
        }
        return ret;
    }
};

class Solution {
    vector<string> ret;
    string path;
    bool visit[10] = { 0 };
public:
    void dfs(string s, int pos) {
        if (path.size() == s.size()) ret.push_back(path);

        for (int i = 0; i < s.size(); i++) {
            if (visit[i] == false) {
                path.push_back(s[i]);
                visit[i] = true;
                dfs(s, i + 1);
                visit[i] = false;
                path.pop_back();
            }
        }
    }
    vector<string> permutation(string S) {
        dfs(S, 0);
        return ret;
    }
};